package com.chj.jz.dp.class06;

public class Code07_WildcardMatching {
	/*
	 * @param s: A string
	 * 
	 * @param p: A string includes "?" and "*"
	 * 
	 * @return: is Match?
	 */
	public static boolean isMatch(String ss, String pp) {
		char[] s = ss.toCharArray();
		char[] p = pp.toCharArray();
		int m = s.length;
		int n = p.length;
		boolean[][] f = new boolean[m + 1][n + 1];
		int i, j;
		for (i = 0; i <= m; ++i) {
			for (j = 0; j <= n; ++j) {
				if (i == 0 && j == 0) {
					f[i][j] = true;
					continue;
				}

				if (j == 0) {
					f[i][j] = false;
					continue;
				}

				f[i][j] = false;
				if (p[j - 1] != '*') {
					if (i > 0 && (p[j - 1] == '?' || p[j - 1] == s[i - 1])) {
						f[i][j] |= f[i - 1][j - 1];
					}
					
				} else {
					f[i][j] |= f[i][j - 1];
					if (i > 0) {
						f[i][j] |= f[i - 1][j];
					}
				}
			}
		}

		return f[m][n];
	}
	
	 /**
     * @param s: A string 
     * @param p: A string includes "." and "*"
     * @return: A boolean
     */

    // 去掉所有 /* ... */ 的注释可以打印solution
    public static boolean isMatch02(String ss, String pp) {
        char[] A = ss.toCharArray();
        char[] B = pp.toCharArray();
        int m = A.length;
        int n = B.length;
        int i, j;
        boolean[][] f = new boolean[m + 1][n + 1];
        int[][] pi = new int[m + 1][n + 1];
        for (i = 0; i <= m; ++i) {
            for (j = 0; j <= n; ++j) {
                if (i == 0 && j == 0) {
                    f[i][j] = true;
                    continue;
                }
                
                if (j == 0) {
                    // i > 0
                    f[i][j] = false;
                    continue;
                }
                
                f[i][j] = false;
                // j > 0
                if (B[j - 1] != '*') {
                    if (i > 0 && (A[i - 1] == B[j - 1] || B[j - 1] == '?')) {
                        pi[i][j] = 1; // A and B cuts tail
                        f[i][j] |= f[i - 1][j - 1];
                    }
                }
                else {
                    //f[i-1][j] OR f[i][j-1]，如果B[j-1]=‘*’
                    f[i][j] |= f[i][j - 1];
                    if (f[i][j - 1] == true) {
                        pi[i][j] = 2; // B cuts *
                    }
                    
                    if (i > 0) {
                        f[i][j] |= f[i - 1][j];
                        if (f[i - 1][j] == true) {
                            pi[i][j] = 3; // B's * at least matches A's tail
                        }
                    }
                }
            }
        }
        
        if (f[m][n]) {
            // res[i] represents that A[i] is matched against B[res[i]]
            int[] res = new int[m];
            i = m;
            j = n;
            while (true) {
                if (j == 0) break;
                if (pi[i][j] == 1) {
                    res[i - 1] = j - 1;
                    --i;
                    --j;
                }
                else {
                    if (pi[i][j] == 2) {
                        --j;
                    }
                    else {
                        res[i - 1] = j - 1;
                        --i;
                    }
                }
            }
            
            for (i = 0; i < m; ++i) {
                System.out.println(A[i] + " matches " + B[res[i]]);
            }   
        }
        
        return f[m][n];
    }
	
	public static void main(String[] args) {
		// 输入: "ABCD" and "EDCA"
		{
			String str1 = "aa";
			String str2 = "a";
			System.out.println(isMatch(str1, str2));
		}
		{
			String str1 = "aa";
			String str2 = "aa";
			System.out.println(isMatch(str1, str2));
		}
		{
			String str1 = "aaa";
			String str2 = "aa";
			System.out.println(isMatch(str1, str2));
		}
		{
			String str1 = "aa";
			String str2 = "*";
			System.out.println(isMatch(str1, str2));
		}
		{
			String str1 = "aa";
			String str2 = "a*";
			System.out.println(isMatch(str1, str2));
		}
		{
			String str1 = "aab";
			String str2 = "c*a*b*";
			System.out.println(isMatch(str1, str2));
			System.out.println("=======");
			System.out.println(isMatch02(str1, str2));
		}
		{
			String str1 = "ab";
			String str2 = "?*";
			System.out.println(isMatch(str1, str2));
			System.out.println(isMatch02(str1, str2));
		}
	}
}
